\section{Related Work}
Existing studies
\cite{choi12:HadoopXML,damigos13:XPath_MapReduce,cong12:PE_XPath} on
evaluating XPath queries over distributed (or fragmented) XML documents
dealt only with top-down path queries (also known as twig patterns),
which compose a small subset of navigational XPath queries. To
the best of our knowledge, navigational XPath queries over distributed documents
have never been seriously investigated.

It is worth noting that applying MapReduce \cite{dean08:MapReduce} to large-scale XML
processing was well studied
\cite{choi12:HadoopXML,damigos13:XPath_MapReduce,sauer13:BrackitMR,choi14:labeling_XML_MapReduce,wu14:structural_join_MapReduce}.
MapReduce enables transparent and fault-tolerant processing on clusters,
while encoding XPath queries on it incurs overheads in various aspects.
In order to minimize overheads and achieve high performance on clusters,
dedicated in-memory processing is more appropriate than MapReduce-based
processing. VXQuery \cite{carman15:VXQuery} has been designed without
MapReduce for this reason but still been under development. At least,
how to process navigational XPath queries in VXQuery was not described in
\cite{carman15:VXQuery}.

Apart from parallel and/or distributed processing, efficient evaluation
of more expressive subsets of XPath was studied
\cite{brantner05:XPath_Natix,grust02:accel_XPath_all_axes,arroyuelo15:SXSI}.
Brantner et al. \cite{brantner05:XPath_Natix} studied efficient
compilation of XPath 1.0 with the internal algebra of an underlying XML
database engine.  Grust \cite{grust02:accel_XPath_all_axes} accelerated
evaluation of all axes with an indexing technique. SXSI
\cite{arroyuelo15:SXSI} dealt with forward Core XPath and all text
predicates in a succinct index structure. We similarly have used two
indices represented with a dedicated data structure for accelerating
query evaluation. We, however, do not claim that these indices and
representation are technically better than existing ones. 
We have experimentally demonstrated that the
two cheap indices in the straightforward representation based on partial
trees suffice for achieving high performance processing of navigational XPath
queries over large-scale documents, not only on a single computer but also
clusters---this is our technical contribution.

%\todo{sato}{To describe communication efficiency of query evaluation based partial trees in earlier sections}
